class Solution {
    List<List<Integer>> re = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] have = new boolean[nums.length+1];
        add(nums,have);
        return re;
    }
    public void add(int[] nums, boolean[] have){
        int len = nums.length;
        if(temp.size() == len){
            re.add(new ArrayList<>(temp));
            return;
        }
        for( int i = 0 ; i < len ; i++){
            //不执行，当have[i]在之前用过，或者和i相同
            if(have[i] || (i > 0 && nums[i] == nums[i - 1] && !have[i - 1])) continue;
            have[i] = true;
            temp.add(nums[i]);
            add(nums,have);
            have[i] = false;
            temp.remove(temp.size()-1);
        }
    }
}